package leetcode.year2021.month10;

//64. 最小路径和
public class _21_01MinPathSum64 {
  /**
   * 思路：考虑动态规划的方法，可以得到动态规划方程   f(i)(j) = Math.min(f(i-1)(j),f(i)(j-1)) + f(i)(j).value,
   *
   *
   * @param grid
   * @return
   */
  public int minPathSum(int[][] grid) {
    int[][] resultInt = new int[grid.length][grid[0].length];
    resultInt[0][0] = grid[0][0];
    for (int i = 1; i < grid[0].length; i++) {
      resultInt[0][i] = resultInt[0][i-1] + grid[0][i];
    }
    for (int i = 1; i < grid.length; i++) {
      resultInt[i][0] = resultInt[i-1][0] + grid[i][0];
    }
    for (int i = 1; i < grid.length; i++) {
      for (int j = 1; j < grid[0].length; j++) {
        resultInt[i][j] = Math.min(resultInt[i-1][j], resultInt[i][j-1]) + grid[i][j];
      }
    }
    return resultInt[grid.length-1][grid[0].length-1];
  }

  /**
   * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
   *
   * 说明：每次只能向下或者向右移动一步。
   *
   * 示例 1：
   * 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
   * 输出：7
   * 解释：因为路径 1→3→1→1→1 的总和最小。
   * 示例 2：
   *
   * 输入：grid = [[1,2,3],[4,5,6]]
   * 输出：12
   *
   */
}
